package leetcode;

import java.util.Arrays;

/**
 * @author: trtan
 * @create: 2021-04-19 08:58
 * @description: 下一个序列
 **/
public class Test {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 9, 9};
        solve(arr);
        System.out.println("----------");
        print(arr);
    }

    static void solve(int[] arr) {
        int i = -1;
        while ((i = hasNext(arr)) != -1) {
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j] > arr[i]) {
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                    for (int k = i + 1; k < arr.length; k++) {
                        int p = arr.length - (k - i);
                        if (k >= p) {
                            break;
                        }
                        tmp = arr[k];
                        arr[k] = arr[p];
                        arr[p] = tmp;
                    }
                    break;
                }
            }
            print(arr);
        }
    }

    static int hasNext(int[] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            if (arr[i] > arr[i - 1]) {
                return i - 1;
            }
        }
        return - 1;
    }

    static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ", ");
        }
        System.out.println();
    }
}
